package common.sort;

import java.util.Arrays;

/**
 * 原理:
 * 先以个位进行排序，然后以十位、百位等依次进行排序
 * 排到最后就是一个有序数组
 */
public class RadixSort01 implements Sort {

    @Override
    public void sort(int[] array) {
        int maxNumLength = getMaxLength(getMaxNum(array));
        radixSort(array, maxNumLength);
    }

    void radixSort(int[] array, int maxNumLength) {
        int mod = 10;
        int dev = 1;

        // 从个位开始排序
        for (int i = 0; i < maxNumLength; i++) {
            //创建20个桶
            int[][] countMatrix = new int[mod * 2][0];

            for (int j = 0; j < array.length; j++) {
                int bucket = (array[j] % mod) / dev + mod;
                countMatrix[bucket] = appendArr(countMatrix[bucket], array[j]);
            }

            dev = dev * 10;
            mod = mod * 10;

            // 合并发原数组
            int pos = 0;
            for (int j = 0; j < countMatrix.length; j++) {
                for (int t : countMatrix[j]) {
                    array[pos++] = t;
                }
            }
        }
    }

    int[] appendArr(int oldArray[], int num) {
        int[] newArray = Arrays.copyOf(oldArray, oldArray.length + 1);
        newArray[newArray.length - 1] = num;
        return newArray;
    }

    int getMaxNum(int[] array) {
        int m = array[0];
        for (int t : array) {
            if (t > m) {
                m = t;
            }
        }
        return m;
    }

    int getMaxLength(int n) {
        if (n == 0) {
            return 1;
        }
        int r = 0;
        while (n > 0) {
            n = n / 10;
            r++;
        }
        return r;
    }

}
